1. Field of the Invention
This invention relates to the field of communication. More specifically, the invention comprises a system and method for using communications between two or more peer listeners in order to improve the ability to receive transmitted data.
2. Description of the Related Art
Many modern communication devices have two or more communication links. A good example is a cellular phone with Internet capability. Such phones have a traditional cellular network link—such as GPRS, EDGE, EVDO, 3G, etc. Such phones also have a wireless local area network interface—such as WiFi. The cellular network link has substantial range and connects the device to a broad network of cell towers. However, the cell link has relatively low capacity, longer latency, and is in often heavily loaded by requests from many cell phones.
The WiFi link has limited range, but has a much higher capacity and is often lightly loaded. The WiFi link may also be used for peer-to-peer communications between cell phones in the same area. In this context the cellular network link is referred to as the “sender link” and the WiFi link is referred to as the “peer link.”
Those skilled in the art will realize that the combination of a sender link and a peer link is possible in many applications beyond cellular telephones. One additional example is the existence of satellite data links with individual nodes which are also tied together using a wireless local area network.
The examples may be generalized to encompass many different environments. Many such environments will involve network nodes which come and go, and may even involve sender links to more than one source or multiple simultaneous sources. An area of particular interest is the field of mobile ad hoc networks (“MANETs”). A MANET typically has a changing structure as members enter and leave the network. These often include a “one-to-many” data dissemination pattern, but may also include a “many-to-many” pattern.
An example is “Blue Force Tracking” where a tactical military network seeks to maintain intra-force communication in order to coordinate the force's activities. It is preferable to provide a flexible architecture in this setting, where the system can appropriately disseminate information without requiring knowledge regarding specific routing or hierarchies. It is also preferable to provide a system which can continually operate despite the temporary or permanent loss of one or more nodes.
Researchers have devised several techniques for improving the efficiency of multicast communications in MANETs and tactical edge networks. The term “multicast” means the dissemination of information simultaneously to more than one node that may be interested in receiving the information rather than to only a single node at a time.
Cooperative networking allows the peers of the network to cooperate in order to increase network performance. Techniques such as cooperative data caching and cooperative data recovery promote greater network availability and survivability. Wireless communication is inherently a broadcast medium and the nature of this medium can be exploited to efficiently communicate with groups of nodes at the same operational cost as a communication to a single designated node (a “unicast”). Packet erasure coding may also be used to minimize transmission errors, though this technique reduces efficiency by requiring the transmission of redundant data.
There presently exist several reliable multicast communication protocols that were specifically designed for disseminating information to multiple nodes in a network. These protocols are often realized in the form of “middleware”—meaning software that connects different software components (often components which are running on different computers and possibly even on different operating systems—a common scenario in the field of communication). One existing protocol is known as “NORM,” which stands for NACK-Oriented Reliable Multicast protocol. A “NACK” is a message listing missing data packets which were not received by a receiver. NORM includes a reliability mechanism that is based on the combination of Automatic Repeat Requests (“ARQ's”) and erasure coding.
Another protocol is “OpenPGM” which is an open source version of the Pragmatic General Multicast protocol. Yet another protocol is the JGroups protocol which is a communication middleware included in the “JBoss” middleware. OpenPGM and JGroups represent commercial off-the-shelf technology. Although both these systems were designed for wired communications, they are interesting reference points even for the wireless world.
Reliable multicast protocols fall into one of four categories depending on the mechanisms they employ to ensure reliability. The four mechanisms are: (1) Automatic Retransmission Request (ARQ); (2) gossip-based; (3) Forward Error Correction (“FEC”); and (4) hybrids of the other three.
ARQ-based systems use acknowledgements sent by the receiver (and possibly timeouts) to ensure reliable transmission. In some versions the sender is responsible for missing packet detection while in other versions the receiver will have this duty. In the former case the sender detects the missing packets based on not receiving acknowledgment messages (“ACK's”) from the receiver(s) within a defined time interval. In receiver-initiated versions, the receivers send the list of missing packets (“NACK's”) to the sender whenever the receiver receives a packet out of sequence (which implies that a prior packet is missing). It is also known to use a hybrid ACK/NACK approach.
ARQ-based systems may not scale well when the size of the network and the number of receivers increase. It is also generally true that the sender is exclusively in charge of the retransmission of missing packets (“repair traffic”). This characteristic means that the sender may become quite burdened by repair traffic when a large number of receivers are present.
In gossip-based systems data are sent in a peer-to-peer fashion. Each node receiving data may choose to forward the data to a subset of its neighbors. The decision is made locally, and may be based on probability or heuristic factors (taking network topological details into account). The main disadvantage to this approach is its non-deterministic delivery.
The approach based on Forward Error Correction sends redundant data (such as parity data) that allows a receiver to reassemble some or all of the lost data on its own. Erasure coding is a particular form of FEC that combines a set of k symbols to obtain a larger set of n transformed signals for which there exists a subset of symbols of size h that can be used to recover the original set. If any subset of size h of the transformed set is sufficient to recover the original set, the code is called optimal.
FEC cannot ensure reliability by itself, but it can be coupled with an ARQ-based approach to reduce the packet loss, which results in fewer retransmissions. NORM is a good example of a hybrid approach using ARQ and FEC. This hybrid approach allows the ARQ mechanism greater efficiency when providing repair traffic. As an example, when optimal erasure codes are used, a single repair packet can repair different packets at different receivers.
Erasure coding techniques are encoded at the source and decoded at the receivers. Different coding schemes (known as “network coding”) allow intermediate nodes that receive the message to re-encode it.
An essential aspect of reliable multicast communication protocols is their reliance on underlying routing protocols. Multicast routing protocols build either routing trees or routing meshes. Both are costly to build and maintain in mobile networks where nodes tend to come and go. Many reliable multicast protocols need group-communication primitives to work.
Support for congestion control represents a critical aspect of reliable multicast communication protocols. Congestion control is in fact critical to the performance of mobile ad hoc networks (“MANET's”) in a multicast environment.
Additional Explanation of Existing NORM Protocol and Prototype System:
NORM (NACK-oriented reliable multicast protocol) works well in MANETs and therefore serves as an effective baseline for evaluating the performance of the present invention. NORM implements a hybrid receiver-initiated ARQ-based multicast protocol that uses packet erasure coding. The packet coding is integrated with the ARQ mechanism. While the packet erasure coding can be provided proactively, it is also possible to provide it reactively. In the reactive case, a FEC packet is only sent in response to a NACK. In this way, the overhead introduced by the FEC mechanism is limited. The downside of this approach is slightly higher latency.
A tradeoff between bandwidth use and latency can be reached by using a hybrid between the proactive and reactive methods. A low level of proactive FEC is combined with reactive FEC (when reactive is necessary). NORM computes FEC over blocks of data. Every block of data is divided into a certain number of segments where a certain percentage of these segments contain FEC data. The user may configure the number of data segments containing FEC data.
NORM provides congestion control via a “TCP friendly” algorithm or through an Explicit Congestion Notification algorithm. In order to control congestion, NORM uses specific control packets that are part of its command set.
Additional Explanation of Existing OpenPGM System:
As stated previously, Open PGM is an implementation of the Pragmatic General Multicast protocol. It uses receiver initiated Automatic Repeat Requests (“ARQ's”). The system is reliable in a MANET environment only within a receiver-managed transmit window where the repair traffic is supplied by either the sender of the message or by designated local repairing nodes (“DLR's”). When a receiver detects missing packets, it sends a NACK request (a list of missing data packets) to the source via unicast. NACKs are propagated reliably to the source following the distribution tree of the source. The result is that the source usually receives only a single copy of the NACK.
When the receiving node receives the data packets requested in the NACK, it will “toggle” to a repair state. The receiving node will then propagate the data along its distribution state. If the repair state is not set, it will not propagate the data. This ensures that repair traffic is sent only along the branches that reach the requesting node. PGM senders can also use forward error correction. OpenPGM also uses a TCP friendly congestion control algorithm.
Additional Explanation of JGroups System:
JGroups is a toolkit for reliable multicast communication that is part of the JBoss suite of Java middleware. JGroups provides a configurable protocol stack that lets the user choose between the different protocols of the channel. In the jargon of JGroups, a channel is a group communication end-point. The channel is comprised of several blocks that implement network protocols. JGroups offers different alternative protocols for each block. The stack's blocks are, in top-down order, as follows: flow control, group membership, reliable delivery, failure detection, discovery, and transport.
The system and method proposed in the present invention is particularly applicable to mobile ad-hoc networks (MANETs) having two separate means of available communication (a sender link and a peer link). The system shifts repair traffic from the sender link to the peer link. The system and method is also advantageous when it is more efficient and/or less expensive to communicate with peers as opposed to the original sender, even if they all share the same communications link.